package editor.cn;
class Solution121{
    public static void main(String[] args) {
        Solution solution = new Solution121().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxProfit(int[] prices) {
        //方法1：传统的一次遍历，两个维护
        //return iter(prices);

        //   方法2：
        return dp(prices);
    }

        private int dp(int[] prices) {
            int n = prices.length;
            if (n == 0) return 0;
            int minprice = prices[0];
            int[] dp = new int[n];//dp[i]表示第i天能够有的最大利润
            dp[0] = 0;

            for (int i = 1; i < n; i++) {
                minprice = Math.min(minprice, prices[i]);//还是基于这样一个事实，对每一个当前值进行对比。最小值对比，最大值对比。
                dp[i] = Math.max(dp[i - 1], prices[i] - minprice);
            }
            return dp[n - 1];
        }

        private int iter(int[] prices) {
            //    在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

            //    那么我们直接保存一个最小值，在保存一个最大利润值。在每一个价格，将其与最小值作对比，如果是比最小值还小，那么就维护他成为最小值，如果比最小值大，那么就
            //      算一算他与前面的最小值的差值是不是大于我们的最大利润值，如果是，那么就更新最大利润值，如果不是，那就直接不管。这样到最后维护的就是最大利润差值。

            int maxProfit=0;
            int minPrice= prices[0];
            for (int i = 1; i < prices.length ; i++) {
                if (prices[i]<minPrice){
                    minPrice= prices[i];
                }
                else if ((prices[i]-minPrice)>maxProfit) {
                    maxProfit= prices[i]-minPrice;
                }
            }
            return maxProfit;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}